use std::iter::Rev;
use std::{borrow::BorrowMut, cell::RefCell, collections::btree_map::Range};

use rayon::iter;

/// 数组问题
/// https://leetcode.cn/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-100-liked
// 53. 最大子数组和
/// 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
// 子数组是数组中的一个连续部分。
// TIP: 直接动态规划 划分子问题，确定无后效性（一定可以由其他子问题求解或者递推）
// p[i] = max(p[i-1],p[i-1]+nums[i]), p[i]代表以i结尾的数组和的最值
pub fn max_sub_array(nums: Vec<i32>) -> i32 {
    let mut max = nums[0];
    let mut pre = 0;
    for x in nums {
        pre = std::cmp::max(pre + x, x);
        max = std::cmp::max(max, pre);
    }

    max
}

#[test]
pub fn test_max_sub_array() {
    println!("{}", max_sub_array(vec![-2, 1, -3, 4, -1, 2, 1, -5, 4]));
}

/// https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked
// 56. 合并区间
// 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
// 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
// TIP: 优先考虑分组
pub fn merge(intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let mut intervals_cp = intervals.clone();
    intervals_cp.sort_by(|a, b| a[0].cmp(&b[0]));

    let mut ans = vec![];

    let mut first = (0, 0);
    first.0 = intervals_cp[0][0];
    first.1 = intervals_cp[0][1];

    for ele in intervals_cp[1..].iter() {
        if ele[0] <= first.1 {
            first.1 = std::cmp::max(ele[1], first.1);
        } else {
            ans.push(vec![first.0, first.1]);
            first.0 = ele[0];
            first.1 = ele[1];
        }
    }
    ans.push(vec![first.0, first.1]);
    ans
}

#[test]
pub fn test_merge() {
    println!("{:?}", merge(vec![vec![1, 4], vec![2, 3]]));
}

/// https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-100-liked
/// 189. 轮转数组
/// 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
pub fn rotate(nums: &mut Vec<i32>, k: i32) {
    let k = k as usize % nums.len();

    unsafe {
        (&mut *(nums as *const _ as *mut Vec<i32>))[0..nums.len() - k as usize].reverse();
    }
    unsafe {
        (&mut *(nums as *const _ as *mut Vec<i32>))[nums.len() - k as usize..].reverse();
    }
    unsafe {
        (&mut *(nums as *const _ as *mut Vec<i32>))[0..].reverse();
    }
}

#[test]
pub fn test_rotate() {
    let mut test_arr = vec![1, 2, 3, 4, 5, 6, 7];
    rotate(&mut test_arr, 3);
    println!("{:?}", test_arr);
}

/// https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-100-liked
///给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
// 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
// 请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
// 238. 除自身以外数组的乘积
// TIP: 触发关键字，每个元素左边序列构成左前缀和，右边元素序列构成右前缀和
pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
    let (mut l, mut r, len) = (1, 1, nums.len());
    let mut ans = vec![1; nums.len()];
    for (i, &v) in nums.iter().enumerate() {
        ans[i] *= l;
        l *= v;

        ans[len - i - 1] *= r;
        r *= nums[len - i - 1];
    }

    ans
}

#[test]
pub fn test_product_except_self() {
    println!("{:?}", product_except_self(vec![1, 2, 3, 4]));
}

/// https://leetcode.cn/problems/first-missing-positive/description/?envType=study-plan-v2&envId=top-100-liked
/// 41. 缺失的第一个正数
/// 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
//
// 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
// TIP: 技巧题，考虑nums长度和最小值的关系 = min(len+1,nums[i])
pub fn first_missing_positive(nums: Vec<i32>) -> i32 {
    let mut record = vec![0; nums.len() + 2];
    let ans = nums.len();
    for &x in nums.iter() {
        if x > 0 && (x as usize) < record.len() {
            record[x as usize] = 1;
        }
    }
    for (i, &v) in record[1..].iter().enumerate() {
        if v == 0 {
            return (i + 1) as i32;
        }
    }
    ans as i32
}

#[test]
pub fn test_first_missing_positive() {
    println!("{:?}", first_missing_positive(vec![1]));
}

// 最长回文子串
// TIP: 优先考虑动态规划
// dp[i][j] = str[i] == str[j] && dp[i+1][j-1]
// 0,0 / 0,1 / 0,1,2 / 0,1,2,3 /
pub fn longest_loop_substr(message: &String) -> (usize, String) {
    let mut index = 0;
    let mut max = 0;
    let len = message.len();
    let mut dp = vec![vec![false; len]; len];
    for i in 0..len {
        dp[i][i] = true;
    }

    for j in 1..len {
        for i in 0..j {
            dp[i][j] = (dp[i + 1][j - 1] || j - i < 2) && message[i..=i] == message[j..=j];
            if dp[i][j] {
                max = std::cmp::max(j - i + 1, max);
                index = i;
            }
        }
    }

    (index, message[index..index + max].to_owned())
}

#[test]
pub fn test_longest_loop_substr() {
    println!(
        "{:?}",
        longest_loop_substr(&"asdfghjklkjhgfdsa".to_string())
    );
}
